{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Binary Gap"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: binaryGap"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二进制间距"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个正整数 <code>n</code>，找到并返回 <code>n</code> 的二进制表示中两个 <strong>相邻</strong> 1 之间的<strong> 最长距离 </strong>。如果不存在两个相邻的 1，返回 <code>0</code> 。</p>\n",
    "\n",
    "<p>如果只有 <code>0</code> 将两个 <code>1</code> 分隔开（可能不存在 <code>0</code> ），则认为这两个 1 彼此 <strong>相邻</strong> 。两个 <code>1</code> 之间的距离是它们的二进制表示中位置的绝对差。例如，<code>\"1001\"</code> 中的两个 <code>1</code> 的距离为 3 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<ul>\n",
    "</ul>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 22\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>22 的二进制是 \"10110\" 。\n",
    "在 22 的二进制表示中，有三个 1，组成两对相邻的 1 。\n",
    "第一对相邻的 1 中，两个 1 之间的距离为 2 。\n",
    "第二对相邻的 1 中，两个 1 之间的距离为 1 。\n",
    "答案取两个距离之中最大的，也就是 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 8\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>8 的二进制是 \"1000\" 。\n",
    "在 8 的二进制表示中没有相邻的两个 1，所以返回 0 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 5\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>5 的二进制是 \"101\" 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [binary-gap](https://leetcode.cn/problems/binary-gap/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [binary-gap](https://leetcode.cn/problems/binary-gap/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['22', '8', '5']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        last, ans, i = -1, 0, 0\n",
    "        while n:\n",
    "            if n & 1:\n",
    "                if last != -1:\n",
    "                    ans = max(ans, i - last)\n",
    "                last = i\n",
    "            n >>= 1\n",
    "            i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        nn = []\n",
    "        res = 0\n",
    "        while(n):\n",
    "            nn.append(n%2)\n",
    "            n = n // 2\n",
    "\n",
    "        for index, key in enumerate(nn):\n",
    "            if key == 1:\n",
    "                num = 0\n",
    "                for j in range(index + 1, len(nn)):\n",
    "                    if nn[j] == 1:\n",
    "                        res = max(j - index, res)\n",
    "                        break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        x = bin(n)[2:].split('1')[1:-1]\n",
    "        if x is None:\n",
    "            return 0\n",
    "        max = 0 \n",
    "        for i in x:\n",
    "            if len(i)+1>max:\n",
    "                max = len(i)+1\n",
    "        return  max"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        prev = -1   # 前一个1的位置\n",
    "        i = 0\n",
    "        while n:\n",
    "            if n & 1:\n",
    "                if prev != -1:\n",
    "                    ans = max(ans, i - prev)\n",
    "                prev = i\n",
    "            n >>= 1\n",
    "            i += 1\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        # 转换成二进制 nn的转置才为真正的二进制\n",
    "        nn = []\n",
    "        res = 0\n",
    "        while(n):\n",
    "            nn.append(n%2)\n",
    "            n = n // 2\n",
    "        # 快慢指针\n",
    "        for index,i in enumerate(nn):\n",
    "            if i == 1:\n",
    "                num = 0\n",
    "                for j in range(index+1, len(nn)):\n",
    "                    if nn[j] == 1:\n",
    "                        num = j - index\n",
    "                        break\n",
    "                if num > res:\n",
    "                    res =num\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        s = bin(n)[2:]\n",
    "        lst = []\n",
    "        ans = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == \"1\":\n",
    "                lst.append(i)\n",
    "        if len(lst) == 1:\n",
    "            return 0\n",
    "        for j in range(len(lst) - 1):\n",
    "            ans = max(ans, lst[j + 1] - lst[j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        res, count1, count2 = 0, 0, 0\n",
    "        while n > 0:\n",
    "            if n&1 == 1:\n",
    "                count2 += 1\n",
    "                if count2 == 2:\n",
    "                   res = max(res, count1)\n",
    "                   count1, count2 = 1, 1\n",
    "                else:\n",
    "                    count1 += 1\n",
    "            elif count2 == 1:\n",
    "                count1 += 1\n",
    "            n >>= 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        count = 1\n",
    "        for c in bin(n)[3:]:\n",
    "            if c == '1':\n",
    "                ans = max(ans, count)\n",
    "                count = 1\n",
    "            else:\n",
    "                count += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        # 转换成二进制 nn的转置才为真正的二进制\n",
    "        nn = []\n",
    "        res = 0\n",
    "        while(n):\n",
    "            nn.append(n%2)\n",
    "            n = n // 2\n",
    "        # 快慢指针\n",
    "        for index,i in enumerate(nn):\n",
    "            if i == 1:\n",
    "                num = 0\n",
    "                for j in range(index+1, len(nn)):\n",
    "                    if nn[j] == 1:\n",
    "                        res = max(j - index, res)\n",
    "                        break\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        m = bin(n)[2:]\n",
    "        res=0\n",
    "        bes=0\n",
    "        for i in range(len(m)):\n",
    "            if m[i]=='1':\n",
    "                res=max(res,i-bes)\n",
    "                bes=i\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        s = bin(n)\n",
    "        i, j = 0, 2\n",
    "        num = 0\n",
    "        while(j< len(s)):\n",
    "            if s[j] == '1':\n",
    "                if i != 0:\n",
    "                    num = max(num, j-i)\n",
    "                \n",
    "                i = j\n",
    "            \n",
    "            j += 1\n",
    "        \n",
    "        return num\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        isexist = False\n",
    "        length = 0\n",
    "        res = 0\n",
    "        while n > 0:\n",
    "            if n % 2 == 1 and (not isexist):\n",
    "                isexist = True\n",
    "                length = 0\n",
    "            elif n % 2 == 1 and isexist:\n",
    "                res = max(res, length + 1)\n",
    "                length = 0\n",
    "            else:\n",
    "                length += 1\n",
    "            n = n >> 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def binaryGap(self, n: int) -> int:\r\n",
    "        s=str(bin(n))\r\n",
    "        left=10**9\r\n",
    "        res=0\r\n",
    "        right=0\r\n",
    "        while n:\r\n",
    "            x=n%2\r\n",
    "            if x==1:\r\n",
    "                res=max(res,right-left)\r\n",
    "                left=right\r\n",
    "            right+=1\r\n",
    "            n//=2\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        prev = -1   # 前一个1的位置\n",
    "        for i in range(31):\n",
    "            if (n >> i) & 1:\n",
    "                if prev != -1:\n",
    "                    ans = max(ans, i - prev)\n",
    "                prev = i\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        cur, last, res = 0, -1, 0\n",
    "        while n > 0:\n",
    "            if n & 1 == 1:\n",
    "                if last != -1:\n",
    "                    res = max(res, cur - last)\n",
    "                last = cur\n",
    "            n >>= 1\n",
    "            cur += 1\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        last, ans, i = -1, 0, 0\n",
    "        while n:\n",
    "            if n & 1:\n",
    "                if last != -1:\n",
    "                    ans = max(ans, i - last)\n",
    "                last = i\n",
    "            n >>= 1\n",
    "            i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def binaryGap(self, n: int) -> int:\r\n",
    "        s=str(bin(n))\r\n",
    "        left=len(s)\r\n",
    "        res=0\r\n",
    "        for i,x in enumerate(s):\r\n",
    "            if x=='1':\r\n",
    "                res=max(res,i-left)\r\n",
    "                left=i\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        prev = -1   # 前一个1的位置\n",
    "        i = 0\n",
    "        while n:   # 时间O(logN)\n",
    "            if n & 1:\n",
    "                if prev != -1:\n",
    "                    ans = max(ans, i - prev)\n",
    "                prev = i\n",
    "            n >>= 1\n",
    "            i += 1\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        last, ans, i = -1, 0, 0\n",
    "        while n:\n",
    "            if n & 1:\n",
    "                if last != -1:\n",
    "                    ans = max(ans, i - last)\n",
    "                last = i\n",
    "            n >>= 1\n",
    "            i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def binaryGap(self, n: int) -> int:\r\n",
    "        dis, pos = 0, -1\r\n",
    "        i = 1\r\n",
    "        while n:\r\n",
    "            if n % 2 == 1:\r\n",
    "                if pos != -1 and i - pos > dis:\r\n",
    "                    dis = i - pos\r\n",
    "                pos = i\r\n",
    "            i += 1\r\n",
    "            n >>= 1\r\n",
    "        return dis"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... \n",
    "        s = bin(n)[2:]\n",
    "        prev = -1\n",
    "        res = 0\n",
    "        for i,ch in enumerate(s):\n",
    "            if ch == '1':\n",
    "                if prev != -1:\n",
    "                    res = max(res, i - prev)\n",
    "                prev = i\n",
    "        return res\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "            res=[] #记录下标\n",
    "            ind=0  \n",
    "            while n :\n",
    "                if n&1==1:\n",
    "                    res.append(ind)\n",
    "                ind+=1\n",
    "                n>>=1\n",
    "            if len(res)<=1:\n",
    "                return 0 #特殊情况\n",
    "            return max([res[i+1]-res[i] for i in range(0,len(res)-1)]) #相邻1的最大值"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        x = bin(n)[2:].split('1')[1:-1]\n",
    "        if x is None:\n",
    "            return 0\n",
    "        max = 0 \n",
    "        for i in x:\n",
    "            if len(i)+1>max:\n",
    "                max = len(i)+1\n",
    "        return  max"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        last = -1\n",
    "        i = 0\n",
    "        while n:\n",
    "            if n&1:\n",
    "                if last != -1:\n",
    "                    ans = max(ans, i-last)\n",
    "                last = i\n",
    "            n >>= 1\n",
    "            i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        en, st = None, None\n",
    "        res = i = 0\n",
    "        while n:\n",
    "            x = n % 2\n",
    "            if x:\n",
    "                if en is None:\n",
    "                    en = i\n",
    "                else:\n",
    "                    res = max(res, i - en)\n",
    "                    en = i\n",
    "            n //= 2\n",
    "            i += 1\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        prebit = -1\n",
    "        for i in range(32):\n",
    "            if (n >> i) & 1:\n",
    "                if prebit != -1:\n",
    "                    ans = max(ans,i - prebit)\n",
    "                prebit = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def binaryGap(self, n: int) -> int:\r\n",
    "        stack = 0\r\n",
    "        length = 0\r\n",
    "        ans = 0\r\n",
    "        while n:\r\n",
    "            item = n&1\r\n",
    "            if item:\r\n",
    "                if stack:\r\n",
    "                    ans = max(ans, length+1)\r\n",
    "                    length = 0\r\n",
    "                else:\r\n",
    "                    stack = 1\r\n",
    "            elif stack:\r\n",
    "                length += 1\r\n",
    "            n >>= 1\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        astr = str(bin(n))[2:]\n",
    "        left = 0\n",
    "        res = 0\n",
    "        for i in range(len(astr)):\n",
    "            if astr[i] == '1':\n",
    "                res = max(res,i-left)\n",
    "                left = i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        a=bin(n)[2:]\n",
    "        return 0 if a.count('1')==1 else len(max(a.split('1')[:-1]))+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        \n",
    "        n = bin(n).removeprefix('0b')\n",
    "        \n",
    "        if n.count('1') < 2:\n",
    "            return 0\n",
    "        \n",
    "        PosOfOne = []\n",
    "        \n",
    "        for i in range(len(n)):\n",
    "            if n[i] == '1':\n",
    "                PosOfOne.append(i)\n",
    "        \n",
    "        maxd = 0\n",
    "        \n",
    "        for i in range(len(PosOfOne)-1):\n",
    "            maxd = max(PosOfOne[i+1] - PosOfOne[i], maxd)\n",
    "            \n",
    "        return maxd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        nums = []\n",
    "        while n != 0:\n",
    "            nums.append(n % 2)\n",
    "            n = n // 2\n",
    "        left = None\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] == 1 and left is None:\n",
    "                left = i\n",
    "            elif nums[i] == 1 and left is not None:\n",
    "                res = max(res, i - left)\n",
    "                left = i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        res = []\n",
    "        str1 = str(bin(n))\n",
    "        if str1.count('1') == 1:\n",
    "            return 0\n",
    "        else:\n",
    "            for i in range(2,len(str1)):\n",
    "                if str1[i] == '1':\n",
    "                    for j in range(i+1,len(str1)):\n",
    "                        if str1[j] == '1':\n",
    "                            res.append(j-i)\n",
    "                            break\n",
    "        return max(res)\n",
    "                        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        # n = bin(n)\n",
    "        # n = n[2:]\n",
    "        # dis = []\n",
    "        # for i in range(len(n)):\n",
    "        #     if n[i] == '1':\n",
    "        #         dis.append(i)\n",
    "        # if len(dis) == 1:\n",
    "        #     return 0\n",
    "        # max_dis = dis[1] - dis[0]\n",
    "        # if len(dis) == 2:\n",
    "        #     return max_dis\n",
    "        # for i in range(1,len(dis)):\n",
    "        #     distance = dis[i] - dis[i-1]\n",
    "        #     max_dis = max(max_dis, distance)\n",
    "        # return max_dis\n",
    "\n",
    "        n = bin(n)[2:]\n",
    "        last = 0\n",
    "        dis = []\n",
    "        for i,char in enumerate(n):\n",
    "            if char == '1' and i != 0:\n",
    "                dis.append(i-last)\n",
    "                last = i\n",
    "        return max(dis) if dis else 0\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        n = bin(n)[2:]\n",
    "        start = -1\n",
    "        end  = -1\n",
    "        res = 0\n",
    "        for index, item in enumerate(n):\n",
    "            if item == \"1\":\n",
    "                if start ==-1:\n",
    "                    start = index\n",
    "                elif end == -1:\n",
    "                    end = index\n",
    "                else:\n",
    "                    start,end = end,index\n",
    "            if start>=0 and end>0:\n",
    "                res = max(res,end-start)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        s = bin(n)[2:]\n",
    "        ans = 0\n",
    "        count = 0\n",
    "        cur = 0\n",
    "        max_num = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '1' and count == 0 :\n",
    "                ans = i\n",
    "                count += 1\n",
    "            elif s[i] == '1' and count == 1 :\n",
    "                ans = i\n",
    "                max_num = max(max_num , cur + 1)\n",
    "                cur = 0\n",
    "            else:\n",
    "                cur += 1\n",
    "        return max_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        pos = []\n",
    "        result = 0\n",
    "        two = bin(n).lstrip('0b')\n",
    "        for i in range(len(two)):\n",
    "            if two[i] == '1':\n",
    "                pos.append(i)\n",
    "        if len(pos) == 1 or len(pos) == 0:\n",
    "            return 0\n",
    "        else:\n",
    "            for j in range(len(pos)-1):\n",
    "                if pos[j+1] - pos[j] > result:\n",
    "                    result = pos[j+1] - pos[j]\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        bin_ = bin(n)[2:]\n",
    "        max_ = 0\n",
    "        start = 0\n",
    "        end = 1\n",
    "        print(bin_)\n",
    "        for _ in range(len(bin_)):\n",
    "            if bin_[_] == '1':\n",
    "                start = _\n",
    "                break\n",
    "        while end <= len(bin_) - 1:\n",
    "            if bin_[end] == '1':\n",
    "                max_ = max(max_, end - start)\n",
    "                start = end\n",
    "            end += 1\n",
    "        return max_\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        result = 0\n",
    "        last_one,now = 0,-1\n",
    "        find_first = False\n",
    "        while n > 0:\n",
    "            now = now + 1\n",
    "            if n % 2 == 1:\n",
    "                if not find_first:\n",
    "                    find_first = True\n",
    "                else:\n",
    "                    if now - last_one > result:\n",
    "                        result = now - last_one\n",
    "                last_one = now\n",
    "            n = int(n / 2)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        b = '{:b}'.format(n).strip('0').split('1')[1:-1]\n",
    "        print(b)\n",
    "        return 1+max(len(s) for s in b) if b else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        index = 0\n",
    "        one_index = []\n",
    "        while n > 0:\n",
    "            if n & 1 == 1:\n",
    "                one_index.append(index)\n",
    "            n = n >> 1\n",
    "            index += 1\n",
    "        one_len = len(one_index)\n",
    "        if one_len < 2: return 0\n",
    "        res = 0\n",
    "        for i in range(1, one_len):\n",
    "            res = max(res, one_index[i] - one_index[i-1])\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def binaryGap(self, n: int) -> int:\r\n",
    "        s=str(bin(n))\r\n",
    "        left=10**9\r\n",
    "        res=0\r\n",
    "        right=0\r\n",
    "        while n:\r\n",
    "            x=n%2\r\n",
    "            if x==1:\r\n",
    "                res=max(res,right-left)\r\n",
    "                left=right\r\n",
    "            right+=1\r\n",
    "            n>>=1\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        pt = -1\n",
    "        cnt = 0\n",
    "        while n:\n",
    "            if n % 2 == 1:\n",
    "                if pt == -1:\n",
    "                    pt = cnt\n",
    "                if pt != -1:\n",
    "                    ans = max(ans,cnt-pt)\n",
    "                    pt=cnt\n",
    "            n//=2\n",
    "            cnt+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        last, ans, i = -1, 0, 0\n",
    "\n",
    "        while n:\n",
    "            if n&1:\n",
    "                if last != -1:\n",
    "                    ans = max(ans, i-last)\n",
    "                last = i\n",
    "            n >>= 1\n",
    "            i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        b = bin(n)[2::]\n",
    "        if b.count(\"1\") >= 2:\n",
    "            ans = 0\n",
    "            cnt = 0\n",
    "            for i in b:\n",
    "                cnt += 1\n",
    "                if i == \"1\":\n",
    "                    ans = max(ans, cnt)\n",
    "                    cnt = 0\n",
    "        else:\n",
    "            return 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        n = bin(n)[2:]\n",
    "        lt, rt = -1, 0\n",
    "        ans = 0\n",
    "        while rt < len(n):\n",
    "            if n[rt] == '1':\n",
    "                if lt != -1:\n",
    "                    ans = max(ans, rt -lt)\n",
    "                lt = rt\n",
    "            rt += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        last, ans, i = -1, 0, 0\n",
    "        while n:\n",
    "            if n & 1:\n",
    "                if last != -1:\n",
    "                    ans = max(ans, i - last)\n",
    "                last = i\n",
    "            n >>= 1\n",
    "            i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        # n = bin(n)\n",
    "        # n = n[2:]\n",
    "        # dis = []\n",
    "        # for i in range(len(n)):\n",
    "        #     if n[i] == '1':\n",
    "        #         dis.append(i)\n",
    "        # if len(dis) == 1:\n",
    "        #     return 0\n",
    "        # max_dis = dis[1] - dis[0]\n",
    "        # if len(dis) == 2:\n",
    "        #     return max_dis\n",
    "        # for i in range(1,len(dis)):\n",
    "        #     distance = dis[i] - dis[i-1]\n",
    "        #     max_dis = max(max_dis, distance)\n",
    "        # return max_dis\n",
    "\n",
    "        n = bin(n)[2:]\n",
    "        last = 0\n",
    "        dis = []\n",
    "        dis.append(0)\n",
    "        for i,char in enumerate(n):\n",
    "            if char == '1' and i != 0:\n",
    "                dis.append(i-last)\n",
    "                last = i\n",
    "        return max(dis)\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        return 1+max((len(s) for s in '{:b}'.format(n).strip('0').split('1')[1:-1]), default=-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        res = []\n",
    "        str1 = str(bin(n))\n",
    "        if str1.count('1') == 1:\n",
    "            return 0\n",
    "        else:\n",
    "            for i in range(len(str1)):\n",
    "                if str1[i] == '1':\n",
    "                    for j in range(i+1,len(str1)):\n",
    "                        if str1[j] == '1':\n",
    "                            res.append(j-i)\n",
    "                            break\n",
    "        return max(res)\n",
    "                        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        last = -1\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        while n:\n",
    "            if n & 1 == 1:\n",
    "                if last != -1:\n",
    "                    ans = max(ans, i - last)\n",
    "                last = i\n",
    "            i += 1\n",
    "            n >>= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        s = bin(n) # bin(8)返回0b1000\n",
    "        s = s[2:].lstrip('0')   # 去掉0b，再去掉前缀0\n",
    "        s = s.rstrip('0')   # 去掉后缀0\n",
    "        lst = s.split('1')\n",
    "        ans = 0\n",
    "        for s in lst:\n",
    "            ans = max(ans, len(s))\n",
    "        return 0 if len(lst) <= 2 else ans + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        last, ans, i = -1, 0, 0\n",
    "        while n:\n",
    "            if n & 1:\n",
    "                if last != -1:\n",
    "                    ans = max(ans, i - last)\n",
    "                last = i\n",
    "            n >>= 1\n",
    "            i += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        str = bin(n)[2:]\n",
    "        maxLen = right = left = 0\n",
    "        while(right < len(str)):\n",
    "            if str[right] == '1':\n",
    "                if right-left > maxLen:\n",
    "                    maxLen = right - left\n",
    "                left = right\n",
    "            right+=1\n",
    "        return maxLen\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        res=0\n",
    "        bg=-1\n",
    "        i=0\n",
    "        while n>0:\n",
    "            if n%2 : \n",
    "                if bg==-1: bg=i  ##首次出现1\n",
    "                res=max(res,i-bg)\n",
    "                bg=i\n",
    "            n=n // 2\n",
    "            i+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        last, ans, i = -1, 0, 0\n",
    "        while n:\n",
    "            if n & 1:\n",
    "                if last != -1:\n",
    "                    ans = max(ans, i - last)\n",
    "                last = i\n",
    "            n >>= 1\n",
    "            i += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        bin_n = bin(n)[2:]\n",
    "        ans = 0\n",
    "        last = 0\n",
    "        for i in range(len(bin_n)):\n",
    "            if bin_n[i] == '1':\n",
    "                ans = max(ans, i - last)\n",
    "                last = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        bin_n = bin(n)[2:]\n",
    "        ans = 0\n",
    "        last = 0\n",
    "        for i in range(len(bin_n)):\n",
    "            if bin_n[i] == '1':\n",
    "                ans = max(ans, i - last)\n",
    "                last = i\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        n = str(bin(n)[2:])\n",
    "        ans = 0\n",
    "        pre = -1\n",
    "        for i in range(len(n)):\n",
    "            if n[i] == '1':\n",
    "                if pre != -1:\n",
    "                    ans = max(ans, i - pre)    \n",
    "                pre = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        a=bin(n)[2:]\n",
    "        last=-1\n",
    "        result=0\n",
    "        for i in range(len(a)):\n",
    "            c=a[i]\n",
    "            if c=='1':\n",
    "                if last>=0:\n",
    "                    dis=i-last\n",
    "                    if dis>result:\n",
    "                        result=dis\n",
    "                last=i\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # length = 0\n",
    "    def binaryGap(self, n: int) -> int:\n",
    "        # binary = bin(n)[2:]\n",
    "        # i, j = 0, 0\n",
    "        # maxnum = 0\n",
    "        # while j < len(binary):\n",
    "        #     if i != j and binary[j] == '1':\n",
    "        #         i = j\n",
    "        #     maxnum = max(maxnum, self.length)\n",
    "        #     self.length = 0\n",
    "        #     while j < len(binary) and binary[j] == '0' or j == i:\n",
    "        #         j += 1\n",
    "        #         self.length += 1\n",
    "        #     if j == len(binary) - 1 and binary[j] == '1':\n",
    "        #         maxnum = max(maxnum, self.length)\n",
    "        # return maxnum\n",
    "        res = 0\n",
    "        left = 0\n",
    "        binary = bin(n)[2:]\n",
    "        for i in range(len(binary)):\n",
    "            if binary[i] == '1':\n",
    "                res = max(res, i - left)\n",
    "                left = i\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
